package com.tuling.code.algorithm.sort;

public class BubbleSort extends Sort {

	@Override
	public void sort(int[] a) {
		int len = a.length;
		System.out.println("排序前：");
		display(a);
		for (int i = 1; i < len; i++) {
			for (int j = 0; j < len - i; j++) {
				if (a[j] > a[j + 1]) {
					int temp = a[j + 1];
					a[j + 1] = a[j];
					a[j] = temp;
				}
			}

			System.out.println("第" + i + "步的排序结果：");
			display(a);
		}
	}

	// 优化之后的
	public void bubbleSort2(int[] a, int n) {
		int j, k = n;
		int times = 1;
		boolean flag = true;// 发生了交换就为true, 没发生就为false，第一次判断时必须标志位true。
		while(flag){
			flag = false;
			for(j = 1 ; j<k; j++){
				if(a[j-1] > a[j]){  //前面的数大于后面的数 ,交换
					a[j-1] = a[j-1]^a[j];
					a[j] = a[j-1]^a[j];
					a[j-1] = a[j-1]^a[j];
					
					//表示交换过数据
					flag = true;
				}
			}
			k--; //减少一次排序的边界
			System.out.println("第"+times + "次排序结果：");
			times ++;
			display(a);
		}
	}
	
	/**
	 * 算法改进
	 * 设置一个标志，如果这一趟发生了交换，则为true，否则为false。明显如果有一趟没有发生交换，说明排序已经完成。
	 * @param a
	 * @param n
	 */
	public void selfSrot(int []a , int n){
		System.out.println("排序前：");
		display(a);
		int j , k = n;
		boolean flag = true;
		int times = 0;
		while(flag){
			flag = false;
			for(j = 1; j<k; j++){
				if(a[j-1] > a[j]){
					int temp = a[j-1];
					a[j-1] = a[j];
					a[j] = temp;
					//一旦发生交换了，将flag设置为true
					flag = true;
				}
			}
			//排序完一次，边界减少1
			k--;
			times ++;
		}
		
		System.out.println("排序后：");
		display(a);
		System.out.println("总排序次数："+times);
	}
	
	/**
	 * 最终的终极冒泡排序方案
	 * 再进一步做优化。
	 * 比如，现在有一个包含1000个数的数组，仅前面100个无序，后面900个都已排好序且都大于前面100个数字，
	 * 那么在第一趟遍历后，最后发生交换的位置必定小于100，且这个位置之后的数据必定已经有序了，也就是这个位置以后的数据不需要再排序了，
	 * 于是记录下这位置，第二次只要从数组头部遍历到这个位置就可以了。如果是对于上面的冒泡排序算法2来说，虽然也只排序100次，
	 * 但是前面的100次排序每次都要对后面的900个数据进行比较，而对于现在的排序算法3，只需要有一次比较后面的900个数据，之后就会设置尾边界，
	 * 保证后面的900个数据不再被排序。
	 * @param a
	 * @param len
	 */
	public void finalSort(int []a , int n){
		System.out.println("排序前：");
		display(a);
		int k;
		int times = 0;
		//flag来记录最后交换的位置，也就是排序的尾边界
		int flag = n;
		
		while(flag > 0){  //排序未结束状态
			k = flag;  //k记录遍历的尾边界
			flag = 0; //强制改为结束状态
			for(int j = 1; j <k ;j++){
				if(a[j-1] > a[j]){
					//交换
					int temp = a[j];
					a[j-1] = a[j];
					a[j] = temp;
					
					//表示交换过数据
					flag = j; //记录最新的边界
				}
			}
			times ++;
		}
		
		System.out.println("排序后：");
		display(a);
		System.out.println("总共排序次数："+times);
		
	}
	
	public void selfFinalSort(int []a , int n){
		int k;
		int flag = n;
		while(flag > 0){
			k = flag;
			flag = 0;
			for(int j = 1; j <k;j++){
				if(a[j-1] > a[j]){
					int temp = a[j];
					a[j] = a[j-1];
					a[j-1] = temp;
					
					flag = j;
				}
			}
		}
		display(a);
	}
	
	public static void main(String[] args) {
		//int[] a = {1, 100, 2, 0, 9, 3, 12, 7, 8, -3, 4, 65, 22};
		int[] a = {1, 3, 2, -1, 0, 4, 4,7 ,8, 9, 10,11, 12, 13,14,15,16,17,18,19,20};
		BubbleSort st = new BubbleSort();
		//st.bubbleSort2(a, a.length);
		//st.sort(a);
		//st.bubbleSort2(a, a.length);
		//st.selfSrot(a, a.length);
		//st.finalSort(a, a.length);
		st.selfFinalSort(a, a.length);
	}
}
